Push-down Automata
Q1.
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet \{Z_0, X\} where Z_0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) \rightarrow (t, XZ_0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_0 and X (in that order) on the stack. (s, a, Z_0) \rightarrow (s, XXZ_0) (s, \epsilon, Z_0) \rightarrow (f, \epsilon) (s, a, X) \rightarrow (s, XXX) (s, b, X) \rightarrow (t, \epsilon) (t, b, X) \rightarrow (t,\epsilon) (t, c, X) \rightarrow (u, \epsilon) (u, c, X) \rightarrow (u, \epsilon) (u, \epsilon, Z_0) \rightarrow (f, \epsilon) The language accepted by the PDA isQ2.
In a pushdown automaton P=(Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form, where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents(q,Y) \in \delta(p,a,X) Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}. The number of strings of length 100 accepted by the above pushdown automaton is ___________Q4.
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described asQ5.
Let L_1 be the set of all languages accepted by a PDA by final state and L_2 the set of all languages accepted by empty stack. Which of the following is true?Q6.
Consider the NPDA \langle Q=\{q_{0},q_{1},q_{2}\}, \Sigma =\{0,1\}, \Gamma =\{0,1,\perp \},\delta ,q_{0},\perp , F=\{q_{2}\} \rangle, where (as per usual convention) Q is the set of states, \Sigma is the input alphabet, \Gamma is the stack alphabet, \delta is the state transition function, q_{0} is the initial state, \perp is the initial stack symbol, and F is the set of accepting states. The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?Q7.
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?Q8.
Consider the transition diagram of a PDA given below with input alphabet \Sigma ={a,b} and stack alphabet \Gamma={X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?Q9.
Let M=(K, \Sigma, \Gamma, \Delta, s, F) be a pushdown automaton, where K=(s, f), F=\{f\}, \Sigma=\{a, b\}, \Gamma=\{a\} \text { and } \Delta=\{((s, a, \epsilon),(s, a)),((s, b, \epsilon),(s, a)),((s, a, a),(f, \epsilon)),((f, a, a),(f, \epsilon)) ((f, b, a),(f, \epsilon))\}Which one of the following strings is not a member of L(M)?Q10.
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be \Sigma. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?